레드-블랙 트리(Red-Black Tree)

이진 트리의 문제점을 보완한 트리(Tree)

일반적인 이진 탐색 트리는 트리의 높이만큼 시간이 걸린다
값이 전체 트리에 고루 분산되어 있다면 문제가 없으나, 데이터가 들어올 때 값이 한 쪽으로 편향되게 들어올 경우, 한쪽으로 크게 치우친 트리가 되어 기존 O(logN)의 탐색 속도가 최악의 경우 O(N) 으로 아주 비효율적이게 된다

이 점을 보완하여 스스로 균형을 잡는 트리가 레드-블랙 트리이다
부모 노드보다 작은 값을 가지는 노드는 왼쪽 자식으로, 큰 값을 가지는 노드는 오른쪽 자식으로 배치하여 데이터의 추가나 삭제 시 트리가 한쪽으로 치우쳐지지 않도록 균형을 맞춰 탐색 속도 O(logN)이 보장된다